#include <iostream>

using namespace std;

class Solution {
private:
    bool is_gcd(string main, string aux) {
        for (int i = 0; i < main.size(); i += aux.size()) {
            for (int j = 0; j < aux.size(); j++) {
                if (main[i + j] != aux[j]) {
                    return false;
                }
            }
        }
        return true;
    }
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1.size() == 0 || str2.size() == 0) {
            return "";
        }
        string large, small;
        if (str1.size() > str2.size()) {
            large = str1;
            small = str2;
        } else {
            large = str2;
            small = str1;
        }
        if (large.size() % small.size() == 0) {
            if (is_gcd(large, small)) {
                return small;
            }
        }
        for (int j = small.size() - 1; j > 0; j--) {
            if (small.size() % j == 0) {
                string aux = small.substr(0, j);
                if (is_gcd(small, aux)) {
                    if (is_gcd(large, aux)) {
                        return aux;
                    }
                }
            }
        }
        return "";
    }
};